package offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author Elephas
 * @Date 2022/1/16
 **/
public class ThreeSum {

    public static void main(String[] args) {
        final int[] TEST01 = new int[]{-1,0,1,2,-1,-4};
        threeSum(TEST01);
    }
    /*
        给定一个数组，找去其中三个值相加为 0 的数
        排序 + 双指针

     */


    public static List<List<Integer>> threeSum(int nums[]){
        Arrays.sort(nums);

        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){
                break;
            }else if(i > 0 && nums[i]==nums[i-1]){
                continue;
            }else{
                // 双指针
                int left = i+1;
                int right = nums.length - 1;
                while(left < right){
                    if(nums[left]+nums[right]+nums[i] == 0){
                        List<Integer> temp = new ArrayList<>();
                        ans.add(temp);
                        temp.add(nums[left]);
                        temp.add(nums[right]);
                        temp.add(nums[i]);
                        left++;
                        right--;
                        while(left < right) {
                            if (nums[left] == nums[left - 1]) {
                                left++;
                            } else {
                                break;
                            }
                        }
                        while(left < right){
                            if(nums[right] == nums[right+1]){
                                right--;
                            }else{
                                break;
                            }
                        }
                    }else if(nums[left]+nums[right]+nums[i] < 0){
                        left++;
                    }else{
                        right--;
                    }
                }
            }
        }
        return ans;
    }

}
